package hw;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class SplitPrice {

    public static void main(String[] args) {
        SplitPrice splitPrice = new SplitPrice();
        splitPrice.splitPrice(new int[]{2, 10, 3, 20, 12});
    }

    private void splitPrice(int[] nums) {
        int length = nums.length;
        // 存放的是下标
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            // 如果当前数比前面数大，从尾巴开始出
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                Integer integer = deque.removeLast();
                result[integer] = (nums[i] - nums[integer]) * (i - integer);
            }
            deque.addLast(i);
        }
        while (!deque.isEmpty()) {
            Integer integer = deque.removeFirst();
            result[integer] = nums[integer];
        }
        System.out.println(Arrays.toString(result));
    }

}
